#define _CRT_SECURE_NO_WARNINGS

#include<stack>
#include<iostream>
#include<string>
#include<vector>

using namespace std;


//栈01：删除字符串中的所有相邻重复元素
class Solution1 {
public:
    string removeDuplicates(string s) 
    {
        string tmp;
        for(auto it:s)
        {
            if(tmp.empty()||it!=tmp.back())
                tmp.push_back(it);
            else            
                tmp.pop_back();            
        }
        return tmp;
    }    
};


//栈02：比较含退格的字符串
class Solution2 {
public:
    bool backspaceCompare(string s, string t) 
    {
        string tmps;
        string tmpt;
        for(auto it:s)
        {
            if(it=='#'&&!tmps.empty())
                tmps.pop_back();                
            else if(it!='#')
                tmps+=it;
            else;
        }
        for(auto it:t)
        {
            if(it=='#'&&!tmpt.empty())
                tmpt.pop_back();                
            else if(it!='#')
                tmpt+=it; 
            else;               
        }
        if(tmps.size()!=tmpt.size())
            return false;
        int len1=0,len2=0;
        while(len1<tmps.size()&&len2<tmpt.size())
        {
            if(tmps[len1]!=tmpt[len2])
                return false;
            len1++;
            len2++;              
        }
        return true;    
    }
};


//栈03：基本计算器II
class Solution3 {
public:
    int calculate(string s) 
    {
        vector<int>  count;
        long tmp=0;
        char op='+';
        int i=0;
        while(i<s.size())
        {
            if(s[i]==' ')
            {
                i++;
                continue;
            }
            else if(s[i]<='9'&&s[i]>='0')//说明it是一个数字
            {
                while(s[i]<='9'&&s[i]>='0'&&i<s.size())
                {
                    tmp=tmp*10+s[i]-'0';
                    i++;
                }
                if (op == '+')
                    count.push_back(tmp);
                else if (op == '-')
                    count.push_back(-tmp);
                else if (op == '*')
                {
                    count.back() *= tmp;
                }
                else if (op == '/')
                {
                    count.back() /= tmp;
                }
                else;
                op=s[i];
                i++;
                tmp=0;
            }
            else
            {                
                op = s[i];
                i++;                
            }
        }
        int ret=0;
        for(auto it:count)
        {
            ret+=it;
        }
        return ret;    
    }
};

//栈04：字符串解码
class Solution4 {
public:
    string decodeString(string s) 
    {
        string stack1;
        string stack2;
        vector<int> count;
        int tmp=0;
        //string ret;
        int i=0;
        while(i<s.size())
        {
            //数字后面跟的一定是方括号
            // if(stack1.empty()&&s[i]<='z'&&s[i]>='a')
            //     ret.push_back(s[i++]);
            if(s[i]<='9'&&s[i]>='0')
            {
                while(s[i]<='9'&&s[i]>='0'&&i<s.size())
                    tmp=tmp*10+s[i++]-'0';
                count.push_back(tmp);
                tmp=0;
            }
            else if(s[i]==']')
            {
                //stack2.push_back(s[i]);
                while(stack1.back()!='[')
                {
                    stack2.push_back(stack1.back());
                    stack1.pop_back();
                }
                stack1.pop_back();//此时stack2里面的内容为xxx，xxx为倒序;
                for(int j=0;j<count.back();j++)
                {
                    stack1.append(stack2.rbegin(),stack2.rend());
                }
                count.pop_back();
                stack2.clear();
                i++;
            }
            else
                stack1.push_back(s[i++]);
        }
        return stack1;
    }
};


//栈05：验证栈序列
class Solution5 {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) 
    {
        if(pushed.size()!=popped.size())
            return false;
        vector<int>  stack1;
        vector<int>  stack2(popped.rbegin(),popped.rend());
        int i=0;
        int j=0;
        while(i<popped.size()&&j<pushed.size())
        {
            if(!stack1.empty()&&stack1.back()==stack2.back())
            {
                stack1.pop_back();
                stack2.pop_back();
                i++; 
                //if(j<pushed.size()-1)j++;
            }
            else
            {
                while(j<pushed.size()-1&&pushed[j]!=popped[i])    stack1.push_back(pushed[j++]);
                stack1.push_back(pushed[j++]);
                if(j>=pushed.size()-1&&stack1.back()!=stack2.back())    return false;
            }            
        }
        while (!stack1.empty())
        {
            if (stack1.back() == stack2.back())
            {
                stack1.pop_back();
                stack2.pop_back();
            }
            else return false;
        }
        return true;
    }
};

//栈05：验证栈序列(优化算法逻辑）
class Solution6 {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) 
    {
        if(pushed.size()!=popped.size())
            return false;
        vector<int>  stack1;
        int j=0;
        for(auto it:pushed)
        {
            stack1.push_back(it);
            while(!stack1.empty()&&stack1.back()==popped[j])
            {
                stack1.pop_back();
                j++;
            }
        }
        return j>=popped.size();
    }
};


void test1()
{
    string s = {" 3+5 / 2 "};
    Solution3 SL;
    cout<<SL.calculate(s);
    return;
}

void test3(vector<int>& tmp)
{
    return;
}

void test2()
{
    vector<int> push = { 1,0,3,2 };
    vector<int> pop = { 0,1,2,3 };
    Solution5 SL;
    if (SL.validateStackSequences(push, pop))
        cout << "1";
    else
        cout << "0";
    //test3({1,2,3});
    return;
}










int main()
{
    test2();
    return 0;
}
